package com.mamingchao.basic.swardToOffer.one;

/**
 * > 题目一
 * 给定一个有序数组arr,代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n-1],
 * 给定一个正数L,代表一根长度为L的绳子,求绳子最多能覆盖其中的几个点
 * >> 关键点： 滑动窗口，不要走回头路，只滑动一遍
 * >> 计算出预备表
 */
public class IssueOne {


    // 第一步，计算出每两个节点之间的距离的数组；比如原始的数组[2,3,7,8,10]，计算出[1,4,1,2],即每个节点之间的距离数组
    private static int[] getDistanceBetweenNodes(int[] originArr){
        int[] distanceArrBetweenNodes = new int[originArr.length-1];

        for (int i = 0; i < originArr.length-1; i++) {
            distanceArrBetweenNodes[i] = originArr[i+1] - originArr[i];
        }
        return distanceArrBetweenNodes;
    }


    // 第二步, 单向遍历数组2，计算覆盖最多的节点
    // 从此方法看出 ，该方式 时间复杂度为O(N平方)
    private static  int getCoverdNodesNum(int[] arr, int lengthOfRope ){

        int[] distanceArrBetweenNodes = getDistanceBetweenNodes(arr);

        int maxCoveredNodeNum = 0;
        for (int i = 0; i < distanceArrBetweenNodes.length; i++) {
            int curSum = 0;
            int j = i;
            int curCounter = 0;

            while (j < distanceArrBetweenNodes.length &&  (curSum + distanceArrBetweenNodes[j]) <= lengthOfRope) {
                curSum += distanceArrBetweenNodes[j++];
                curCounter ++;
            }

            if (curCounter + 1 > maxCoveredNodeNum)
                maxCoveredNodeNum = curCounter + 1;
        }
        return  maxCoveredNodeNum;
    }

    // 利用大于等于某个值最左侧的点，和小于等于某个值最右侧的点；以数组上的一个点为绳子的起点或者终点，然后把绳子拉直，然后求一个虚拟的终点或者起点
    // 再利用 大于等于某个值最左侧的点，和小于等于某个值最右侧的点求 终点和起点最近的 数组上的index； 用两个点的index 相减加一




    public static void main(String[] args) {
        int[] arr = {2,3,7,8,10};
        final int lengthOfRope = 2;

        int maxCoveredNodeNum = getCoverdNodesNum(arr, lengthOfRope);

        System.out.println(maxCoveredNodeNum);
    }
}
